1. Field of the Invention
The invention relates to a method for motion estimation in video coding, more particularly to motion estimation methods utilizing a distance-weighted search sequence to find a best-matched motion vector.
2. Description of the Related Art
Referring to FIG. 1, the data structure of a data stream of an MPEG coded video is shown to be formed from one or more sequences. Each sequence includes a group of pictures (GOP), which refers to a group consisting of a plurality of pictures or frames. These pictures or frames can be classified into three types, i.e., intra-coded frames (I frame), predictive-coded frames (P frame), and bi-directionally predictive-coded frames (B frame), according to their attributes.
Each of the aforesaid frames can be encoded. Generally, I frames are used as cut-in points during video compression. A P frame can be predicted through motion estimation using an I frame or another P frame as a reference frame, whereas a B frame can be predicted from the motion vectors generated by both an I frame and a P frame or by two P frames which serve as reference frames. Thus, by playing the frames successively, an MPEG video can be presented to a user.
Each frame can be divided into a plurality of slices. Each slice is further divided into a plurality of macroblocks (MB). Each macroblock is composed of four luminance blocks and a plurality of chrominance blocks. Each block is defined as the smallest coded unit of the MPEG data structure. The corresponding inverse operation of motion compensation in MPEG compression standards is motion estimation. The most direct way of implementing motion estimation is to record the luminance and chrominance of each pixel of a macro block or a block, and match all blocks/macroblocks in the search area to find the best matched macroblock or block. This method is called full search.
With the use of motion estimation and motion compensation techniques, the blocks in a reference frame can be adjusted to become those in a current frame by using the blocks in the current frame and the best matched blocks found from the reference frame for calculating motion vectors and differential data. Blocks can be shifted to proper positions according to the motion vectors, whereas the differential data provide changes in the luminance, chrominance, and saturation values. Since it is not necessary to record a large amount of redundant data, the amount of stored data can be reduced to thereby achieve the object of data compression.
Referring to FIG. 2, the aforesaid method of finding a best matched block from a reference frame can be exemplified using a conventional determination scheme, i.e., the Three-Step Search (TSS). First, the center of a search area 21 to be searched is defined as an origin point T0, and eight points on the boundary of the search area 21 serve as check points. Supposing the size of the search area 21 is 4×4, and a check point T1 at the lower right corner of the search area 21 is the best matched point, the check point T1 is chosen as the new center, and the search area 21 is reduced to a new search area 22 with a size of 2×2. Finally, when a check point T2 at the upper right corner of the search area 22 is found to be the new best matched point, a motion vector value can be estimated thereon.
Referring to FIG. 3, another conventional determination scheme is the Diamond Search (DS), in which a search area in the shape of a diamond is searched. This search scheme involves the following steps:
Step 1: An origin point and eight other points that surround the origin point and that lie on the boundary of a diamond-shaped search area are found so that there are altogether nine search points. If the best matched point is found to be at the center of the search area, the flow proceeds to step 4. On the other hand, if the best matched point is found to be on the boundary of the search area, the flow proceeds to step 2.
Step 2: The search is continued using another set of check points on the boundary of another diamond-shaped search area that is centered at the best matched point found in step 1.
Step 3: If the best matched point is still found to be at the center of the new search area, step 4 is performed. On the other hand, if the new best matched point is found to be on the boundary of the new search area, step 2 is repeated.
Step 4: The search area is reduced to a smaller diamond. The search is stopped when the ideal point is found.
The aforesaid scheme is further illustrated with reference to FIG. 3A. In step 1, the initial best matched point is found to be at the center (1a) of the search area, and step 4 is therefore performed in a reduced search area, a smaller diamond. The search is ended when the ideal point (2a) is located.
Referring to FIG. 3B, when the initial best matched point (1b) in step 1 is found to be located on the boundary of the search area, step 2 is performed to form another diamond-shaped search area centered at the initial best matched point (1b). Then step 3 is performed. Since the new best matched point (2b) is found to lie on the boundary of the new search area, step 2 is repeated to form yet another diamond-shaped search area centered at the new best matched point (2b). When it is found that the latest best matched point is located at the center of the search area, step 4 is performed in a reduced search area, a smaller diamond. The search is ended when the ideal point (4b) is found.
Regardless of which conventional determination scheme is used, a raster search order (see FIG. 4A) or a rectangular spiral search order (see FIG. 4B) may be employed. The so-called raster search order is to find the best matched point from a predefined search area by searching from left to right and then from top to bottom. The so-called rectangular spiral search pattern begins at the center of a predefined search area, and moves outward in a spiral fashion to cover each check point.